# 通过DFS判断图中是否存在环

from collections import defaultdict, deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        
        # 初始化入度
        indegree = [0] * numCourses
        # 初始化课程先验关系
        adj = defaultdict(list)

        for cur, pre in prerequisites:
            indegree[cur] += 1
            adj[pre].append(cur)

        # 把入度为0的加入队列
        q = deque()
        for i in range(numCourses):
            if indegree[i] == 0:
                q.append(i)

            
        while q:

            n = len(q)
            for i in range(n):
                pre = q.popleft()
                numCourses -= 1

                for cur in adj[pre]:

                    indegree[cur] -= 1

                    if indegree[cur] == 0:
                        q.append(cur)
        
        return numCourses == 0




if __name__ == "__main__":
    
    num = 2
    pre = [[1,0]]

    sol = Solution()
    res = sol.canFinish(num, pre)
    print(res)

